/*
给定每天的温度，求对于每一天需要等几天才能等到更暖和的一天，如果该天之后不存在更暖和的天气，则记为0


输入是一个一维整数数组，输出是同样长度的整数数组，表示对于每天需要等待多少天

Input: [73, 74, 75, 71, 69, 72, 76, 73]
Output: [1, 1, 4, 2, 1, 1, 0, 0]


*/
vector<int> dailyTemperatures(vector<int> &temperatures)
{
    int n = temperatures.size();
    vector<int> ans(n);
    stack<int> indices;
    for (int i = 0; i < n; ++i)
    {
        while (!indices.empty())
        {
            int pre_index = indices.top();
            if (temperatures[i] <= temperatures[pre_index])
            {
                break;
            }
            indices.pop();
            ans[pre_index] = i - pre_index;
        }
        indices.push(i);
    }
    return ans;
}
